Communication networks comprise a large number of interconnected network nodes, such as terminals, routers and switches. Data is communicated through a network by passing protocol data units, such as Internet Protocol (IP) packets, Ethernet frames or data cells between nodes. A particular protocol data unit may travel along a path through many such nodes and communication links and a network of this kind should efficiently route the protocol data units between nodes.
A wide range of routing protocols are known. Most routing protocols require each routing node to maintain a database of network information. This requires the node to exchange network information with other nodes and to process and store the information. One form of calculation is to construct a tree of shortest paths across the network, based on the information received from nodes. The above requirements place a significant processing burden on the nodes. The exchange of routing information can use a significant portion of the total bandwidth which could otherwise be used for carrying traffic, particularly in networks where the topology changes on a frequent basis, such as in wireless ad-hoc networks.
There exists a class of networks in which traffic patterns are very focused. The traffic in these networks generally flows either from a well known focal point out to all the other nodes, or the reverse, from all those nodes back to the focal point. In these networks rarely, if ever, does traffic flow in any other pattern. One example of a network that generally exhibits these characteristics is a wireless ad-hoc network containing a network of wireless routers spanning a neighborhood and providing wireless access to individual users in the neighborhood. In this type of network it is desirable to distribute traffic across a number of different routes so as to avoid congestion along particular links or nodes, particularly those closest to the focal node.
A U.S. patent application with U.S. Ser. No. 10/745,886, filed 23 Dec. 2003, the contents of which are incorporated herein by reference, describes a way of performing constraint based routing on a network in which traffic passes through a focal node. A source (i.e. the focal node) can specify a route which is to be followed by a target. A target can then use this routing to send traffic to the focal node. In this way, the focal node can more evenly distribute traffic across the nodes within the network.
It is desirable to use a routing scheme which minimises the amount of resources required in each node and which minimises the signalling overhead.